The seminal work of Parekh and Gallager, entitled “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks, The multiple node case”, EEEE/ACM Trans. Networking, vol. 2-2, pages 137-150, April 1994, has shown that it is possible to provide Quality of service (QoS) guarantees in an Internet Protocol (IP) network. Their techniques require certain fundamental additions to the networking infrastructure, including (1) admission control, (2) marking of admitted traffic so that the network routers and switches can associate it with an admitted flow, (3) policing of admitted traffic to make sure that it does not exceed its promised demand on network resources, and (4) managing and queuing traffic from admitted flows in certain ways in the core of the network to ensure that the service promised to admitted flows is not compromised by congestion in other portions of the network.
The initial QoS solution for IP networks, Integrated Services (IntServ), was directly inspired by the work of Parekh and Gallager, supra. That approach requires that network elements provide separate queuing for each admitted flow and entails the maintenance of per-flow state in each network element. IntServ approaches also tend to make admission decisions locally, rather than based on a network-wide policy.
Differentiated Services (DiffServ) is an approach to providing QoS to aggregate flows. It may provide satisfactory QoS without needing per-flow state in each network element. Additionally, in conjunction with a Bandwidth Broker for admission control, the DiffServ-based approach can support admission control that is driven by network-wide policies. Our delay bound techniques are readily applicable to layer-2 networks that support class of service (CoS), as CoS and DiffServ provide similar differentiated aggregate flow traffic treatment.
DiffServ uses aggregate flows in the sense that multiple flows share the same queue in the network core. Additional analysis is needed to bound the impact of aggregation of flows. Providing-end-to-end QoS requires the presence of individual network elements that have sufficiently strong QoS behavior, together with an analysis of network-wide accumulation of traffic bursts.
The analysis for aggregated flows relies on approaches where it is known that in the absence of bounds on the total number of network elements and on the maximum path length, it is possible to construct pathological scenarios in which no delay bound can be met. Fortunately, there are many situations where bounded delay can be achieved. These include networks where there is a known bound on the maximum number of hops taken by any flow. Many important networks, such as enterprise networks or networks confined to a ship or other vehicle are of bounded size and hence have a determinable upper bound on the number of hops taken by any flow.
Within a bounded network, there may be a small fraction of traffic that is so time-fragile that deterministic bounds on delay are important, a much larger fraction of less fragile, but still time-sensitive traffic for which approximate, probabilistic QoS is sufficient, and an even larger fraction for which best-effort delivery is completely satisfactory. To support this scenario of differentiated service requirements, without resorting to separate queues for individual flows, the network core would treat packets according to an aggregate classification. To respect the requirements of a more sensitive aggregate, the treatment could be one based on a strict priority, or it could be based on weighted sharing discipline. In any case, admissions need to be controlled appropriately while accounting correctly for the treatment of the aggregates.
Motivated by this scenario, the admission calculations in the present invention address this need within a general framework of any number of priority classes and, within each priority class, any number of weighted-share sub-classes.